class Solution
{
public:
    int minimumTotalPrice(int n, vector<vector<int>> &edges, vector<int> &price, vector<vector<int>> &trips)
    {
        // 建图
        vector<vector<int>> adjTable(n);
        for (auto &edge : edges)
        {
            adjTable[edge[0]].push_back(edge[1]);
            adjTable[edge[1]].push_back(edge[0]);
        }

        // 统计每个点被访问的次数
        vector<int> visitCount(n, 0);

        // 对每个 trip 使用 dfs 找到最短路径
        for (auto &trip : trips)
        {
            stack<array<int, 2>> pathStack;
            vector<bool> visited(n, false);
            int start = trip[0];
            int end = trip[1];
            pathStack.push({start, 0});
            visited[start] = true;
            while (!pathStack.empty())
            {
                auto [curNode, nextNodeIndex] = pathStack.top();

                if (curNode == end) // 找到最短路径后更新 visitCount
                {
                    while (!pathStack.empty())
                    {
                        auto [node, _] = pathStack.top();
                        pathStack.pop();
                        ++visitCount[node];
                    }
                    break;
                }
                if (nextNodeIndex == adjTable[curNode].size())
                {
                    pathStack.pop();
                    continue;
                }

                int nextNode = adjTable[curNode][nextNodeIndex];
                ++pathStack.top()[1];
                if (!visited[nextNode])
                {
                    visited[nextNode] = true;
                    pathStack.push({nextNode, 0});
                }
            }
        }

        // 每个节点的总共 price
        vector<int> nodeTotalPrice(n);
        for (int i = 0; i < n; ++i)
        {
            nodeTotalPrice[i] = price[i] * visitCount[i];
        }

        // 建树
        vector<vector<int>> treeChildren(n);
        vector<int> treeParent(n, -1);
        queue<int> q;
        q.push(0); // 任选一个节点当作根
        while (!q.empty())
        {
            int node = q.front();
            q.pop();
            for (int adjNode : adjTable[node])
            {
                if (adjNode != treeParent[node])
                {
                    treeChildren[node].push_back(adjNode);
                    q.push(adjNode);
                    treeParent[adjNode] = node;
                }
            }
        }

        // 在树上 dp
        // dp[0][node] 表示 node 不减半时, node 及其子树的最小 price
        // dp[1][node] 表示 node 减半时, node 及其子树的最小 price
        vector<vector<int>> dp(2, vector<int>(n, 0));

        // 维护叶子节点
        vector<int> unsolvedChildrenCount(n);
        unordered_set<int> toSolve;
        for (int i = 0; i < n; ++i)
        {
            int childrenCount = treeChildren[i].size();
            unsolvedChildrenCount[i] = childrenCount;
            if (childrenCount == 0)
            {
                toSolve.insert(i);
            }
        }

        while (!toSolve.empty())
        {
            // 维护新的叶子节点
            unordered_set<int> nextSolve;
            for (int node : toSolve)
            {
                dp[0][node] = nodeTotalPrice[node];
                dp[1][node] = nodeTotalPrice[node] / 2;

                for (int child : treeChildren[node])
                {
                    dp[0][node] += min(dp[0][child], dp[1][child]); // node不减半, 各个 child 可以选择是否减半
                    dp[1][node] += dp[0][child];                    // node减半, child 必须不减半
                }

                int parent = treeParent[node];
                if (parent == -1)
                {
                    return min(dp[0][0], dp[1][0]);
                }
                --unsolvedChildrenCount[parent];
                if (unsolvedChildrenCount[parent] == 0)
                {
                    nextSolve.insert(parent);
                }
            }
            toSolve.swap(nextSolve);
        }
        return -1;
    }
};